// Queue data structures for GridCut algorithm

use std::collections::VecDeque;

/// A double-ended queue optimized for the GridCut algorithm.
/// 
/// FQueue provides efficient push_back, pop_back, pop_front operations
/// using VecDeque for simplicity and safety.
pub(crate) struct FQueue<T> {
    data: VecDeque<T>,
}

impl<T> FQueue<T> {
    /// Creates a new FQueue with pre-allocated capacity.
    /// 
    /// # Arguments
    /// * `capacity` - Initial capacity to pre-allocate
    pub fn new(capacity: usize) -> Self {
        Self {
            data: VecDeque::with_capacity(capacity),
        }
    }

    /// Pushes an element to the back of the queue.
    pub fn push_back(&mut self, value: T) {
        self.data.push_back(value);
    }

    /// Removes and returns the element from the back of the queue.
    /// 
    /// Returns None if the queue is empty.
    pub fn pop_back(&mut self) -> Option<T> {
        self.data.pop_back()
    }

    /// Removes and returns the element from the front of the queue.
    /// 
    /// Returns None if the queue is empty.
    pub fn pop_front(&mut self) -> Option<T> {
        self.data.pop_front()
    }

    /// Returns a reference to the front element without removing it.
    /// 
    /// Returns None if the queue is empty.
    pub fn front(&self) -> Option<&T> {
        self.data.front()
    }

    /// Clears all elements from the queue.
    pub fn clear(&mut self) {
        self.data.clear();
    }

    /// Returns true if the queue is empty.
    pub fn empty(&self) -> bool {
        self.data.is_empty()
    }
}


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_new_queue_is_empty() {
        let queue: FQueue<i32> = FQueue::new(10);
        assert!(queue.empty());
        assert_eq!(queue.front(), None);
    }

    #[test]
    fn test_push_back_and_pop_front() {
        let mut queue = FQueue::new(5);
        
        queue.push_back(1);
        queue.push_back(2);
        queue.push_back(3);
        
        assert!(!queue.empty());
        assert_eq!(queue.front(), Some(&1));
        assert_eq!(queue.pop_front(), Some(1));
        assert_eq!(queue.pop_front(), Some(2));
        assert_eq!(queue.pop_front(), Some(3));
        assert!(queue.empty());
        assert_eq!(queue.pop_front(), None);
    }

    #[test]
    fn test_push_back_and_pop_back() {
        let mut queue = FQueue::new(5);
        
        queue.push_back(1);
        queue.push_back(2);
        queue.push_back(3);
        
        assert_eq!(queue.pop_back(), Some(3));
        assert_eq!(queue.pop_back(), Some(2));
        assert_eq!(queue.pop_back(), Some(1));
        assert!(queue.empty());
        assert_eq!(queue.pop_back(), None);
    }

    #[test]
    fn test_mixed_operations() {
        let mut queue = FQueue::new(5);
        
        queue.push_back(1);
        queue.push_back(2);
        assert_eq!(queue.pop_front(), Some(1));
        queue.push_back(3);
        assert_eq!(queue.pop_back(), Some(3));
        queue.push_back(4);
        assert_eq!(queue.pop_front(), Some(2));
        assert_eq!(queue.pop_front(), Some(4));
        assert!(queue.empty());
    }

    #[test]
    fn test_clear() {
        let mut queue = FQueue::new(5);
        
        queue.push_back(1);
        queue.push_back(2);
        queue.push_back(3);
        
        assert!(!queue.empty());
        queue.clear();
        assert!(queue.empty());
        assert_eq!(queue.front(), None);
        assert_eq!(queue.pop_front(), None);
    }

    #[test]
    fn test_empty_queue_operations() {
        let mut queue: FQueue<i32> = FQueue::new(5);
        
        assert!(queue.empty());
        assert_eq!(queue.pop_front(), None);
        assert_eq!(queue.pop_back(), None);
        assert_eq!(queue.front(), None);
    }

    #[test]
    fn test_capacity_growth() {
        let mut queue = FQueue::new(2);
        
        // Push more elements than initial capacity
        for i in 0..10 {
            queue.push_back(i);
        }
        
        // Verify all elements are present
        for i in 0..10 {
            assert_eq!(queue.pop_front(), Some(i));
        }
        assert!(queue.empty());
    }

    #[test]
    fn test_front_does_not_remove() {
        let mut queue = FQueue::new(5);
        
        queue.push_back(42);
        assert_eq!(queue.front(), Some(&42));
        assert_eq!(queue.front(), Some(&42));
        assert!(!queue.empty());
        assert_eq!(queue.pop_front(), Some(42));
        assert!(queue.empty());
    }

    #[test]
    fn test_clear_and_reuse() {
        let mut queue = FQueue::new(5);
        
        queue.push_back(1);
        queue.push_back(2);
        queue.clear();
        
        queue.push_back(3);
        queue.push_back(4);
        
        assert_eq!(queue.pop_front(), Some(3));
        assert_eq!(queue.pop_front(), Some(4));
        assert!(queue.empty());
    }
}
